package com.leetcode.partition5;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/5 8:42
 */
public class LC452用最少数量的箭引爆气球 {

    public static int findMinArrowShots(int[][] points) {
        return greedy(points);
    }

    public static void main(String[] args) {
        int[][] points = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
        System.out.println(findMinArrowShots(points));
    }

    private static int greedy(final int[][] points) {
        if (points.length == 0) return 0;
        //根据每个气球的起始点位置进行排序
        Arrays.sort(points, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        int answer = 1;             //至少需要一支箭
        //正序遍历气球，如果points[i][0]>points[i-1][1]，说明当前气球和上一个气球的右侧最小重叠区间不相交，需要一支新箭
        //否则说明当前气球和上一个气球的右侧最小重叠区间相交，只需要points[i-1][1]=Math.min(points[i][1], points[i-1][1])
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > points[i - 1][1]) answer++;
            else points[i][1] = Math.min(points[i][1], points[i - 1][1]);
        }
        return answer;
    }
}
